﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Globalization;
using System.Xml;

namespace eu.h8me.Parsing.ParserLib {

    /// <summary>
    /// Helper class used to encapsulate rule symbols (i.e., non-terminals and terminals). When a symbol contains productions,
    /// it is considered to be a non-terminal, otherwise it is a terminal. See below for more info on how to influence whether
    /// a symbol is considered to be either.
    /// </summary>
    public sealed class Symbol : IEnumerable<Production>, IComparable<Symbol> {

        /// <summary>
        /// Merge callback when a split parse converges back to a single parse tree on reducing a non-terminal.
        /// </summary>
        /// <param name="state">Current parser state, in a MergeState structure.</param>
        /// <param name="data1">Data bound to the first possible parse.</param>
        /// <param name="data2">Data bound to the second possible parse.</param>
        /// <returns>New data value for the merged token.</returns>
        public delegate object MergeEventType(MergeState state, object data1, object data2);

        /// <summary>
        /// Symbol associativity for terminals. Left-associative favors reduce over shift on equal precedence, right-associative
        /// favors shift over reduce on equal precedence, non-associative does not permit any operation.
        /// </summary>
        public enum Associativity {
            Left = 0,
            Right = 1,
            NonAssoc = 2
        };

        // Data.
        private static int NEXT_SYMBOL_ID;
        private readonly Grammar _Grammar;
        private readonly int _ID = NEXT_SYMBOL_ID++;
        private readonly string _Name;
        private object _Tag;
        private int? _Precedence;
        private Associativity? _Associativity;
        private int _ReducePrecedence;
        private event MergeEventType _MergeEvent;
        private List<Production> _Productions = new List<Production>();

        /// <summary>
        /// Initialize a new symbol, bound to the passed grammar with the specified name and symbol identity.
        /// </summary>
        /// <param name="grm">Grammar for symbol.</param>
        /// <param name="name">Name of symbol in grammar.</param>
        internal Symbol(Grammar grm, string name) {
            // Store data.
            _Grammar = grm;
            _Name = name;
        }

        /// <summary>
        /// Access the grammar instance that this symbol stems from.
        /// </summary>
        public Grammar Grammar {
            get {
                // Return defining grammar.
                return _Grammar;
            }
        }

        /// <summary>
        /// Fetch the name of this symbol in the current grammar.
        /// </summary>
        public string Name {
            get {
                // Return defined name.
                return _Name;
            }
        }

        /// <summary>
        /// Get or set the tag bound to this grammar symbol. The symbol tag cannot be (re-)set after the grammar has been
        /// finalized.
        /// </summary>
        public object Tag {
            get {
                // Return tag.
                return _Tag;
            }
            set {
                // Set up tag.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to set symbol tag after grammar is finished");
                _Tag = value;
            }
        }

        /// <summary>
        /// Get or set the symbol precedence of a terminal symbol. When a specific precedence value is set up, this symbol is
        /// irrevocably made a terminal symbol, and may not be used as a non-terminal anymore. A precedence value may only be
        /// set up when the grammar is not finished yet. The base precedence value that is used for terminals when none is set up
        /// explicitly is zero.
        /// </summary>
        public int SymbolPrecedence {
            get {
                // Check value setup.
                if( _Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ) )
                    throw new InvalidOperationException("Trying to get symbol precedence on non-terminal");
                else if( !_Precedence.HasValue && !_Associativity.HasValue )
                    throw new InvalidOperationException("Trying to get symbol precedence when not set up");

                // Fetch precedence.
                return _Precedence.GetValueOrDefault(0);
            }
            set {
                // Set up precedence.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to set symbol precedence when grammar is finished");
                else if( _Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ) )
                    throw new InvalidOperationException("Trying to set precedence on non-terminal");

                // Set up precende and clear productions (we're a non-terminal).
                _Precedence = value;
                _Productions = null;
            }
        }

        /// <summary>
        /// Check whether precedence for a terminal symbol is set up. Precedence is set up if either precedence or associativity
        /// was assigned.
        /// </summary>
        public bool HasSymbolPrecedence {
            get {
                // Check whether precedence. is set up.
                return _Precedence.HasValue || _Associativity.HasValue;
            }
        }

        /// <summary>
        /// Get or set the symbol associativity, which defaults to Left when a specific symbol precedence has been set up. A
        /// symbol associativity may only be set on a terminal, and setting symbol associativity irrevocably makes this symbol be
        /// a terminal. Symbol associativity may only be set up when the grammar is not finished yet.
        /// </summary>
        public Associativity SymbolAssociativity {
            get {
                // Check value setup.
                if( _Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ) )
                    throw new InvalidOperationException("Trying to get associativity on non-terminal");
                else if( !_Precedence.HasValue && !_Associativity.HasValue )
                    throw new InvalidOperationException("Symbol has no defined associtativity");

                // Return value.
                return _Associativity.GetValueOrDefault(Associativity.Left);
            }
            set {
                // Check preconditions.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to set symbol associativity when grammar is finished");
                else if( _Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ) )
                    throw new InvalidOperationException("Trying to set associativity on non-terminal");

                // Set up associativity.
                _Associativity = value;
                _Productions = null;
            }
        }

        /// <summary>
        /// Check whether symbol associativity has been set up for this symbol.
        /// </summary>
        public bool HasSymbolAssociativity {
            get {
                // Check whether associativity is set up.
                return _Precedence.HasValue || _Associativity.HasValue;
            }
        }

        /// <summary>
        /// Return the reduce precedence for this non-terminal, which is used by the parser to decide which reduction paths to
        /// favor.
        /// </summary>
        internal int ReducePrecedence {
            get {
                // Return parse precedence.
                Debug.Assert(_Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ), "Trying to get symbol reduce precedence on terminal");
                return _ReducePrecedence;
            }
            set {
                // Set up parse precedence.
                Debug.Assert(_Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ), "Trying to set symbol reduce precedence on terminal");
                _ReducePrecedence = value;
            }
        }

        /// <summary>
        /// Retrieve or set this symbol to be a (non-)terminal, respective of the value. You may only change the state of a symbol
        /// to be either of the two in case you have not yet set up other relevant flags which force the symbol to be either.
        /// The terminal state may only be set up when the grammar is not finished yet.
        /// </summary>
        public bool IsTerminal {
            get {
                // Return production count; this determines whether this is a terminal.
                return _Productions == null || ( _Productions.Count == 0 && _MergeEvent == null );
            }
            set {
                // Check preconditions.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Cannot set terminal state after grammar finished");
                else if( value && _Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ) )
                    throw new ArgumentException("Cannot set terminal state on symbol when productions present");
                else if( !value && ( _Precedence.HasValue || _Associativity.HasValue ) )
                    throw new ArgumentException("Cannot set symbol to non-terminal when precedence/associativity set");

                // Disable productions.
                _Productions = !value ? new List<Production>() : null;
            }
        }

        /// <summary>
        /// Bind or unbind merge events for this non-terminal. Merge-events may only be bound when this symbol is a non-terminal,
        /// and the grammar this symbol is related to is not finished yet. Binding a merge event forces the symbol to be a
        /// non-terminal.
        /// </summary>
        public event MergeEventType MergeEvent {
            add {
                // Attach an event if finished.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to attach merge event after grammar finish");
                else if( _Productions == null )
                    throw new InvalidOperationException("Illegal merge event to add to terminal");
                else if( value == null )
                    throw new ArgumentNullException("Illegal merge event to add, is NULL");
                _MergeEvent += value;
            }
            remove {
                // Attach an event if finished.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to remove merge event after grammar finish");
                else if( _Productions == null )
                    throw new InvalidOperationException("Illegal merge event to remove from terminal");
                else if( value == null )
                    throw new ArgumentNullException("Illegal merge event to remove, is NULL");
                _MergeEvent -= value;
            }
        }

        /// <summary>
        /// Serialize the current symbol state to an Xml structure.
        /// </summary>
        /// <param name="doc">XML document to serialize to.</param>
        /// <returns>Xml structure of the serialized symbol state.</returns>
        internal XmlNode StoreXML(XmlDocument doc) {
            // Create symbol root node.
            XmlNode xmlsymb = doc.CreateElement("symbol");
            xmlsymb.Attributes.Append(doc.CreateAttribute("name")).InnerText = _Name;

            // Attach symbol specific info.
            if( _Productions == null || ( _Productions.Count == 0 && _MergeEvent == null ) ) {
                // Attach terminal attributes.
                xmlsymb.Attributes.Append(doc.CreateAttribute("type")).InnerText = "terminal";
                if( _Precedence.HasValue )
                    // Attach precedence.
                    xmlsymb.Attributes.Append(doc.CreateAttribute("precedence")).InnerText = _Precedence.Value.ToString(CultureInfo.InvariantCulture);
                if( _Associativity.HasValue )
                    // Attach associativity.
                    xmlsymb.Attributes.Append(doc.CreateAttribute("associativity")).InnerText = _Associativity.Value.ToString();
            } else {
                // Attach non-terminal attributes.
                xmlsymb.Attributes.Append(doc.CreateAttribute("type")).InnerText = "nonterminal";
                xmlsymb.Attributes.Append(doc.CreateAttribute("reduceprecedence")).InnerText = _ReducePrecedence.ToString(CultureInfo.InvariantCulture);

                // Store productions for symbol.
                for( int i = 0; i < _Productions.Count; ++i ) {
                    // Initialize production store.
                    XmlNode xmlprod = xmlsymb.AppendChild(doc.CreateElement("production"));
                    xmlprod.Attributes.Append(doc.CreateAttribute("id")).InnerText = i.ToString(CultureInfo.InvariantCulture);

                    // Store production.
                    _Productions[i].StoreXML(doc, xmlprod);
                }
            }

            // Return created symbol spec.
            return xmlsymb;
        }

        /// <summary>
        /// Serialize the current symbol to the specified output stream as a C# source.
        /// </summary>
        /// <param name="os">Stream to serialize to.</param>
        internal void StoreCS(StreamWriter os) {
            // Create construction line.
            os.Write("symbs[\"{0}\"] = new StoredSymbol(\"{0}\", ", _Name);
            if( _Productions == null || ( _Productions.Count == 0 && _MergeEvent == null ) ) {
                // Store terminal.
                os.Write("StoredSymbol.SymbolType.Terminal, ");
                os.Write("{0}, ", _Precedence.HasValue ? _Precedence.Value.ToString(CultureInfo.InvariantCulture) : "null");
                if( _Associativity.HasValue )
                    // Store actual associativity enum reference.
                    os.WriteLine("Symbol.Associativity.{0});", _Associativity.Value.ToString());
                else
                    // No associativity set up.
                    os.WriteLine("null);");
            } else
                // Store non-terminal.
                os.WriteLine("StoredSymbol.SymbolType.NonTerminal, {0}, null);", _ReducePrecedence.ToString(CultureInfo.InvariantCulture));
        }

        /// <summary>
        /// Store productions attached to this symbol to the output stream.
        /// </summary>
        /// <param name="os">Stream to serialize to.</param>
        internal void StoreProductionsCS(StreamWriter os) {
            // Loop over productions.
            foreach( Production prod in _Productions ) {
                // Attach production set.
                os.Write("symbs[\"{0}\"].Attach(", _Name);
                prod.StoreCS(os);
                os.WriteLine(");");
            }
        }

        /// <summary>
        /// Check the current symbol against the state set up in the specified xml structure, returning true if the symbol maches.
        /// </summary>
        /// <param name="xmlsymb">XML structure of symbol to check against.</param>
        /// <returns>boolean indicating whether structure matches.</returns>
        internal bool CheckXML(XmlNode xmlsymb) {
            // Check symbol specific info.
            if( _Productions == null || ( _Productions.Count == 0 && _MergeEvent == null ) ) {
                // Is a terminal, check terminal specific state.
                bool prec = false;
                bool assoc = false;
                foreach( XmlAttribute attr in xmlsymb.Attributes ) {
                    // Switch on attribute name.
                    if( attr.Name == "type" && attr.InnerText != "terminal" )
                        // Type mismatch.
                        return false;
                    else if( attr.Name == "precedence" ) {
                        // Check precedence match.
                        if( !_Precedence.HasValue || _Precedence.Value != Convert.ToInt32(attr.InnerText, CultureInfo.InvariantCulture) )
                            return false;
                        prec = true;
                    } else if( attr.Name == "associativity" ) {
                        // Check associativity match.
                        if( !_Associativity.HasValue || _Associativity.Value != (Associativity)Enum.Parse(typeof(Associativity), attr.InnerText) )
                            return false;
                        assoc = true;
                    }
                }

                // Check whether associativity and precedence were used.
                if( ( !prec && _Precedence.HasValue ) || ( !assoc && _Associativity.HasValue ) )
                    return false;
            } else {
                // Is a non-terminal, check non-terminal specific state.
                foreach( XmlAttribute attr in xmlsymb.Attributes ) {
                    // Check type.
                    if( attr.Name == "type" && attr.InnerText != "nonterminal" )
                        // Invalid type.
                        return false;
                    else if( attr.Name == "reduceprecedence" )
                        // Store reduce precedence.
                        _ReducePrecedence = Convert.ToInt32(attr.InnerText, CultureInfo.InvariantCulture);
                }
            }

            // Matched.
            return true;
        }

        /// <summary>
        /// Check productions of this non-terminal against the productions defined in the XML structure. In case they match,
        /// initialize mapping between IDs stated in the production dictionary and in this non-terminal.
        /// </summary>
        /// <param name="xmlsymb">XML node to check.</param>
        /// <param name="symbids">Symbol ID dictionary to map to local symbols.</param>
        /// <param name="prodids">Production ID dictionary for this symbol; filled when successful.</param>
        /// <returns>true iff the productions could be matched against local productions.</returns>
        internal bool CheckProductionsXML(XmlNode xmlsymb, Dictionary<string, Symbol> symbids, Dictionary<int, int> prodids) {
            // Build list of productions to check.
            Dictionary<Production, int> tocheck = new Dictionary<Production, int>();
            for( int i = 0; i < _Productions.Count; ++i )
                tocheck[_Productions[i]] = i;

            // Loop over productions in XML document.
            foreach( XmlNode xmlprod in xmlsymb.SelectNodes("production") ) {
                // Match production against current productions remaining to match.
                bool found = false;
                foreach( KeyValuePair<Production, int> prod in tocheck ) {
                    if( prod.Key.CheckXML(xmlprod, symbids) ) {
                        // We have a match; remove it from dictionary and set up prodids dictionary.
                        prodids[Convert.ToInt32(xmlprod.Attributes["id"].InnerText, CultureInfo.InvariantCulture)] = prod.Value;
                        tocheck.Remove(prod.Key);

                        // Set up found state and finish.
                        found = true;
                        break;
                    }
                }

                // Check whether we found any. If not, non-terminal doesn't match.
                if( !found )
                    return false;
            }

            // When we get here, return whether we matched all.
            return tocheck.Count == 0;
        }

        /// <summary>
        /// Check the passed stored symbol against this symbol, returning true if the symbols match.
        /// </summary>
        /// <param name="storsymb">Stored symbol representation.</param>
        /// <param name="prodids">Production IDs.</param>
        /// <returns>Boolean indicating whether the symbol matches.</returns>
        internal bool CheckCS(StoredSymbol storsymb, Dictionary<int, int> prodids) {
            // Check symbol specific info.
            if( _Productions == null || ( _Productions.Count == 0 && _MergeEvent == null ) ) {
                // Check terminal.
                if( storsymb.Type != StoredSymbol.SymbolType.Terminal )
                    // Type doesn't match.
                    return false;
                else if( ( storsymb.Precedence.HasValue && !_Precedence.HasValue ) ||
                    ( !storsymb.Precedence.HasValue && _Precedence.HasValue ) ||
                    ( storsymb.Precedence.HasValue && _Precedence.HasValue && storsymb.Precedence.Value != _Precedence.Value ) )
                    // Precedence doesn't match.
                    return false;
                else if( ( storsymb.Associativity.HasValue && !_Associativity.HasValue ) ||
                    ( !storsymb.Associativity.HasValue && _Associativity.HasValue ) ||
                    ( storsymb.Associativity.HasValue && _Associativity.HasValue && storsymb.Associativity.Value != _Associativity.Value ) )
                    // Associativity doesn't match.
                    return false;
            } else {
                // Check non-terminal.
                if( storsymb.Type != StoredSymbol.SymbolType.NonTerminal )
                    // Type doesn't match.
                    return false;
                _ReducePrecedence = storsymb.Precedence.Value;

                // Build list of productions to check.
                Dictionary<Production, int> tocheck = new Dictionary<Production, int>();
                for( int i = 0; i < _Productions.Count; ++i )
                    tocheck[_Productions[i]] = i;

                // Loop over productions on symbol.
                List<StoredProduction> storprods = storsymb.Productions;
                for( int i = 0; i < storprods.Count; ++i ) {
                    // Match against productions.
                    bool found = false;
                    foreach( KeyValuePair<Production, int> prod in tocheck ) {
                        if( prod.Key.CheckCS(storprods[i]) ) {
                            // We have a match; remove it from to check and enter id.
                            prodids[i] = prod.Value;
                            tocheck.Remove(prod.Key);

                            // Set up found state.
                            found = true;
                            break;
                        }
                    }

                    // Check whether we found any.
                    if( !found )
                        return false;
                }

                // Check whether all were matched.
                if( tocheck.Count > 0 )
                    return false;
            }

            // Matched completely.
            return true;
        }

        /// <summary>
        /// On non-terminals, access the bound production with the specified index.
        /// </summary>
        /// <param name="idx">Index of the production to retrieve.</param>
        /// <returns>Production which is bound to this non-terminal symbol.</returns>
        public Production this[int idx] {
            get {
                // Check index.
                if( _Productions == null || idx < 0 || _Productions.Count <= idx )
                    throw new ArgumentOutOfRangeException("Invalid production index requested");
                return _Productions[idx];
            }
        }

        /// <summary>
        /// Return the number of productions bound to a non-terminal symbol. For terminals, this always returns zero.
        /// </summary>
        public int Count {
            get {
                // Return production count.
                return _Productions != null ? _Productions.Count : 0;
            }
        }

        /// <summary>
        /// Retrieve a typed enumerator listing the productions that are bound to this non-terminal symbol. For terminals, the
        /// returned enumerator is empty.
        /// </summary>
        /// <returns>Typed enumerator over the productions of this non-terminal symbol.</returns>
        public IEnumerator<Production> GetEnumerator() {
            // Return enumerator on productions.
            return _Productions != null ? _Productions.GetEnumerator() : new List<Production>().GetEnumerator();
        }

        /// <summary>
        /// Retrieve an untyped enumerator listing the productions that are bound to this non-terminal symbol. For terminals, the
        /// returned enumerator is empty.
        /// </summary>
        /// <returns>Untyped enumerator over the productions of this non-terminal symbol.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            // Return untyped production enumerator.
            return _Productions != null ? _Productions.GetEnumerator() : new List<Production>().GetEnumerator();
        }

        /// <summary>
        /// Compare the specified symbol to the other, returning a full ordering of them.
        /// </summary>
        /// <param name="other">Symbol to compare against.</param>
        /// <returns>Symbol relation.</returns>
        public int CompareTo(Symbol other) {
            // Check for equal grammar.
            if( _Grammar != other._Grammar )
                throw new InvalidOperationException("Trying to compare symbols from different grammars");
            return _ID.CompareTo(other._ID);
        }

        /// <summary>
        /// Return a short string representation of this symbol.
        /// </summary>
        /// <returns>String representation of this symbol.</returns>
        public override string ToString() {
            // Return name.
            return String.Format("[{0}:{1}terminal:{2}]", _Name, _Productions != null && ( _Productions.Count > 0 || _MergeEvent != null ) ? "non-" : "", _Tag);
        }

        /// <summary>
        /// Attach a production consisting of a single symbol to this non-terminal, forcing the symbol to be a non-terminal.
        /// Productions may only be added when the grammar has not been finished yet.
        /// </summary>
        /// <param name="symb">One-element production to add to non-terminal.</param>
        /// <returns>Finalized production object consisting of the one non-terminal.</returns>
        public Production Add(Symbol symb) {
            // Check whether symbols belong to same grammar.
            if( symb == null )
                throw new ArgumentNullException("Trying to add null symbol as production");
            else if( _Grammar != symb._Grammar )
                throw new ArgumentException("Trying to add symbol of different grammar");
            else if( _Grammar.IsFinished )
                throw new InvalidOperationException("Trying to add symbol to finalized grammar");
            else if( _Productions == null )
                throw new InvalidOperationException("Trying to add production to terminal");

            // Attach the specific symbol as a production to the list of productions.
            Production prod = new Production(symb);
            _Productions.Add(prod);
            prod.Finish();

            // Return production.
            return prod;
        }

        /// <summary>
        /// Attach a pre-built production to this non-terminal, forcing the symbol to be a non-terminal. Productions may only
        /// be added when the grammar has not been finished yet.
        /// </summary>
        /// <param name="prod">Production which has not been finished (i.e., added to a symbol) yet.</param>
        /// <returns>Finished production object, which is equivalent to the parameter.</returns>
        public Production Add(Production prod) {
            // Check whether production belongs to the same grammar.
            if( prod == null )
                throw new ArgumentNullException("Trying to add null production as production");
            else if( _Grammar != prod.Grammar )
                throw new ArgumentException("Trying to add production of different grammar");
            else if( _Grammar.IsFinished )
                throw new InvalidOperationException("Trying to add production to finalized grammar");
            else if( _Productions == null )
                throw new InvalidOperationException("Trying to add production to terminal");
            else if( prod.IsFinished )
                throw new ArgumentException("Trying to re-add finished production to symbol");

            // Attach the specific production to the list of productions.
            _Productions.Add(prod);
            prod.Finish();

            // Return production.
            return prod;
        }

        /// <summary>
        /// Concatenate two symbols to yield a production, consisting of these two symbols.
        /// </summary>
        /// <param name="symb1">First symbol in production.</param>
        /// <param name="symb2">Second symbol in production.</param>
        /// <returns>Unfinished (i.e. unbound) production consisting of the concatenation of these symbols.</returns>
        public static Production operator +(Symbol symb1, Symbol symb2) {
            // Create production from adding two symbols.
            if( symb1 == null || symb2 == null )
                throw new ArgumentNullException("Trying to add null symbols as production");
            return new Production(symb1) + symb2;
        }

        /// <summary>
        /// Concatenate a production to a symbol, returning an unfinished production consisting of the concatenation of the
        /// symbols.
        /// </summary>
        /// <param name="symb">Symbol to prefix to production.</param>
        /// <param name="prod">Unfinished (i.e. unbound) production.</param>
        /// <returns>Unfinished (i.e. unbound) production consisting of the contatenation of the symbol and production.</returns>
        public static Production operator +(Symbol symb, Production prod) {
            // Create production from adding symbol and production.
            if( symb == null || prod == null )
                throw new ArgumentNullException("Trying to add null symbol or production as production");
            return new Production(symb) + prod;
        }

        /// <summary>
        /// Generate a new lexer token from the symbol, binding the attached data to it. This operation is only valid when the
        /// grammar that the symbol is bound to is finished. Token objects are processed by the parser.
        /// </summary>
        /// <param name="symb">Symbol to which to bind data for yielding a lexer token.</param>
        /// <param name="data">Data to bind to the symbol for yielding a lexer token.</param>
        /// <returns>The respective lexer token for the parser to process.</returns>
        public static Token operator /(Symbol symb, object data) {
            // Check whether grammar is finished.
            if( symb == null )
                throw new ArgumentNullException("Trying to create symbolinfo from null symbol");
            else if( !symb._Grammar.IsFinished )
                throw new InvalidOperationException("Trying to create symbolinfo for grammar that's not finished");
            else if( symb._Productions != null && ( symb._Productions.Count > 0 || symb._MergeEvent != null ) )
                throw new InvalidOperationException("Trying to create symbolinfo for non-terminal in grammar");
            else if( symb == symb._Grammar.EOI )
                throw new InvalidOperationException("Trying to attach data to EOI token");

            // Finalize object.
            return new Token(symb, data);
        }

        /// <summary>
        /// Execute a (possibly) bound merge action on this non-terminal, either deciding which production that generated the
        /// symbol to prefer depending on the merge precedence set up with a production, or using the merge event that has been
        /// specified on this non-terminal. In case no merge event has been specified with this production, defer to the merge
        /// event that has possibly been set up with the grammar.
        /// </summary>
        /// <param name="parser">Parser object that generated the merge event.</param>
        /// <param name="data1">Data of the first parse.</param>
        /// <param name="data2">Data of the second parse.</param>
        /// <param name="lex">Current token that was read on input.</param>
        /// <returns>Value to use for the merged target.</returns>
        internal object Merge(Parser parser, StateLink data1, StateLink data2, Token lex) {
            // Check whether both productions have merge precedence set up.
            if( data1.ProductionRule.HasMergePrecedence && data2.ProductionRule.HasMergePrecedence ) {
                // Check equivalence.
                if( data1.ProductionRule.MergePrecedence > data2.ProductionRule.MergePrecedence )
                    // Precedence of data1 is higher than that of data2, (auto-)resolve using data1.
                    return data1.Token.Data;
                else if( data1.ProductionRule.MergePrecedence < data2.ProductionRule.MergePrecedence )
                    // Precedence of data2 is higher than that of data1, (auto-)resolve using data2.
                    return data2.Token.Data;
            }

            // Check whether event is set up (either none/one has merge precedence, or that is equal).
            if( _MergeEvent != null )
                // Yes, dispatch to local merge event.
                return _MergeEvent(new MergeState(_Grammar, parser, this, data1.Production, data2.Production), data1.Token.Data, data2.Token.Data);

            // Call merge event on grammar.
            return _Grammar.Merge(parser, this, data1, data2, lex);
        }

    }

    /// <summary>
    /// Helper class carrying a grammar symbol bound to data, specifically data coming from a lexer process. Instances of this
    /// class should only be produced in the lexing process.
    /// </summary>
    public sealed class Token {

        // Data.
        private static readonly TokenPosition DEFAULT_POSITION = new TokenPosition("", 0, 0, 0, 0);
        private readonly Symbol _Symbol;
        private readonly object _Data;
        private TokenPosition _Position = DEFAULT_POSITION;

        /// <summary>
        /// Initialize a new token instance bound to the specified symbol, with the specified data.
        /// </summary>
        /// <param name="symb">Symbol for lexer token.</param>
        /// <param name="data">Data bound to lexer token.</param>
        internal Token(Symbol symb, object data) {
            // Store info.
            _Symbol = symb;
            _Data = data;
        }

        /// <summary>
        /// Record where a token matched.
        /// </summary>
        /// <param name="pos">Token position.</param>
        internal Token MatchAt(TokenPosition pos) {
            // Store data.
            _Position = pos;
            return this;
        }

        /// <summary>
        /// Access the symbol bound to this lexer token.
        /// </summary>
        public Symbol Symbol {
            get {
                // Return associated symbol.
                return _Symbol;
            }
        }

        /// <summary>
        /// Access the data bound to this lexer token.
        /// </summary>
        public object Data {
            get {
                // Fetch data.
                return _Data;
            }
        }

        /// <summary>
        /// Fetch token position.
        /// </summary>
        public TokenPosition Position {
            get {
                // Return position.
                return _Position;
            }
        }

        /// <summary>
        /// Retrieve a short string representation of the token and its contained data.
        /// </summary>
        /// <returns>String representation of symbol and data bound here.</returns>
        public override string ToString() {
            // Return string representation of symbol info.
            return String.Format("[{0}:{1}]", _Symbol, _Data);
        }

        /// <summary>
        /// Implicitly convert a symbol to a token, with bound data being "null". This is equivalent to using "symb / null".
        /// </summary>
        /// <param name="symb">Symbol to bind.</param>
        /// <returns>New token bound to the specified symbol.</returns>
        public static implicit operator Token(Symbol symb) {
            // Check arguments.
            if( symb == null )
                throw new ArgumentNullException("Trying to create symbolinfo from null symbol");
            else if( !symb.Grammar.IsFinished )
                throw new InvalidOperationException("Trying to create symbolinfo for unfinished grammar");
            else if( !symb.IsTerminal )
                throw new InvalidOperationException("Trying to create symbolinfo for non-terminal");

            // Create new symbolinfo object from plain symbol.
            return new Token(symb, null);
        }

    }

    /// <summary>
    /// Helper class to store a token position.
    /// </summary>
    public sealed class TokenPosition {

        // Data.
        private readonly string _FileName;
        private readonly int _StartLine;
        private readonly int _StartPos;
        private readonly int _EndLine;
        private readonly int _EndPos;

        /// <summary>
        /// Initialize a new token position with the specified arguments.
        /// </summary>
        /// <param name="fname">File name this occurred in.</param>
        /// <param name="startline">Token starting line.</param>
        /// <param name="startpos">Token starting position.</param>
        /// <param name="endline">Token endling line.</param>
        /// <param name="endpos">Token ending position.</param>
        internal TokenPosition(string fname, int startline, int startpos, int endline, int endpos) {
            // Store data.
            _FileName = fname;
            _StartLine = startline;
            _StartPos = startpos;
            _EndLine = endline;
            _EndPos = endpos;
        }

        /// <summary>
        /// Access file name bound to position.
        /// </summary>
        public string FileName {
            get {
                // Return file name.
                return _FileName;
            }
        }

        /// <summary>
        /// Starting line matched at (inclusive).
        /// </summary>
        public int StartLine {
            get {
                // Return starting line.
                return _StartLine;
            }
        }

        /// <summary>
        /// Fetch starting position of token (inclusive).
        /// </summary>
        public int StartPos {
            get {
                // Return starting position.
                return _StartPos;
            }
        }

        /// <summary>
        /// Ending line matched at (exclusive).
        /// </summary>
        public int EndLine {
            get {
                // Return end line.
                return _EndLine;
            }
        }

        /// <summary>
        /// End position matched at (exclusive).
        /// </summary>
        public int EndPos {
            get {
                // Return end position.
                return _EndPos;
            }
        }

        /// <summary>
        /// Join the two token positions, yielding a token position that encompasses the maximum range.
        /// </summary>
        /// <param name="p1">First token position to add.</param>
        /// <param name="p2">Second token position to add.</param>
        /// <returns>Joined token position.</returns>
        public static TokenPosition operator +(TokenPosition p1, TokenPosition p2) {
            // Check that file names match.
            if( p1._FileName != p2._FileName )
                throw new ArgumentException("Illegal positions to add, file names don't match");

            // Join the starting positions to get minimum.
            int startline;
            int startpos;
            if( p1._StartLine < p2._StartLine ) {
                // p1 is the smaller.
                startline = p1._StartLine;
                startpos = p1._StartPos;
            } else if( p1._StartLine > p2._StartLine ) {
                // p2 is the smaller.
                startline = p2._StartLine;
                startpos = p2._StartPos;
            } else {
                // Both are on same line, use char index.
                startline = p1._StartLine;
                startpos = p1._StartPos < p2._StartPos ? p1._StartPos : p2._StartPos;
            }

            // Join the ending positions to get maximum.
            int endline;
            int endpos;
            if( p1._EndLine > p2._EndLine ) {
                // p1 is bigger.
                endline = p1._EndLine;
                endpos = p1._EndPos;
            } else if( p1.EndLine < p2._EndLine ) {
                // p2 is bigger.
                endline = p2._EndLine;
                endpos = p2._EndPos;
            } else {
                // Noth are on same line, use char index.
                endline = p1._EndLine;
                endpos = p1._EndPos > p2._EndPos ? p1._EndPos : p2._EndPos;
            }

            // Return new position token.    
            return new TokenPosition(p1._FileName, startline, startpos, endline, endpos);
        }

        /// <summary>
        /// Return string form of token position.
        /// </summary>
        /// <returns>String form of position.</returns>
        public override string ToString() {
            // Return string.
            return String.Format("file {0}, ({1},{2}) - ({3},{4})", _FileName, _StartLine, _StartPos, _EndLine, _EndPos);
        }

    }

    /// <summary>
    /// Helper class used to carry information concerning a merge action and the current parsing state.
    /// </summary>
    public sealed class MergeState {

        // Data.
        private readonly Grammar _Grammar;
        private readonly Parser _Parser;
        private readonly Symbol _Symbol;
        private readonly int _Production1;
        private readonly int _Production2;

        /// <summary>
        /// Initialize a new merge state object from the passed arguments.
        /// </summary>
        /// <param name="gram">Grammar the merge action took place.</param>
        /// <param name="parser">Parser that is invoking the merge action.</param>
        /// <param name="symb">Symbol that is being merged.</param>
        /// <param name="prod1">Production index (in symbol production set) creating the first possible object data.</param>
        /// <param name="prod2">Production index (in symbol production set) creating the second possible object data.</param>
        internal MergeState(Grammar gram, Parser parser, Symbol symb, int prod1, int prod2) {
            // Store data.
            _Grammar = gram;
            _Parser = parser;
            _Symbol = symb;
            _Production1 = prod1;
            _Production2 = prod2;
        }

        /// <summary>
        /// Retrieve the grammar that created the parser.
        /// </summary>
        public Grammar Grammar {
            get {
                // Return grammar.
                return _Grammar;
            }
        }

        /// <summary>
        /// Retrieve the parser object that invoked the merge action.
        /// </summary>
        public Parser Parser {
            get {
                // Return parser.
                return _Parser;
            }
        }

        /// <summary>
        /// Retrieve the non-terminal symbol for which two different productions are being merged.
        /// </summary>
        public Symbol Symbol {
            get {
                // Return symbol.
                return _Symbol;
            }
        }

        /// <summary>
        /// Retrieve the production object that created the first possible object data.
        /// </summary>
        public Production LeftProduction {
            get {
                // Return left production.
                return _Symbol[_Production1];
            }
        }

        /// <summary>
        /// Retrieve the production object that created the second possible object data.
        /// </summary>
        public Production RightProduction {
            get {
                // Return right production.
                return _Symbol[_Production2];
            }
        }

    }

}
